package tree


/*
二叉树中序遍历
 */

func inorderTraversal(root *TreeNode) []int {
	if root.Left == nil && root.Right == nil {
		return []int{root.Val}
	}
	res := make([]int, 0)
	res = append(res, inorderTraversal(root.Left)...)
	res = append(res, root.Val)
	res = append(res, inorderTraversal(root.Right)...)
	return res
}

func inorderTraversal2(root *TreeNode) []int {
	var list []int
	inorder(root, &list)
	return list
}

func inorder(root *TreeNode, list *[]int) {
	if root != nil {
		inorder(root.Left, list)
		*list = append(*list, root.Val)
		inorder(root.Right, list)
	}
}
